import java.util.*;


public class Dijkstra {


    public static ArrayList<Road> dijkstra(int vs, int end, Intersection[] vertexes, HashMap<Integer, Intersection> int2Index, HashMap<String, Road> roadHashMap) {
        ArrayList<Road> res = new ArrayList<>();
        // Flag [i] = true indicates that the shortest path from "vertex vs" to "vertex i" has been obtained successfully
        boolean[] flag = new boolean[vertexes.length];
        // U is to record the vertex (and the distance from the vertex to the starting point s) whose shortest path has not been worked out, which is used together with flag. Flag [i] = = true indicates that I vertex in U has been removed
        double[] U = new double[vertexes.length];
        // Precursor vertex array, that is, the value of prev [i] is the vertex before "vertex i" in all the vertices experienced by the shortest path from "vertex vs" to "vertex i".
        int[] prev = new int[vertexes.length];
        // The function of S is to record the vertex of the shortest path
        Intersection[] S = new Intersection[vertexes.length];

        // Step 1: at the beginning, there is only the starting point vs in S; the vertex except vs in U, and the path of the vertex in U is "the starting point vs the path to the vertex".
        for (int i = 0; i < vertexes.length; i++) {
            flag[i] = false; // The shortest path of vertex i has not been obtained.
            U[i] = getPrim(vs, i, int2Index, roadHashMap); // The initial distance between vertex i and vertex vs is the weight from "vertex vs" to "vertex i". That is, adjacency matrix vs row data.
            prev[i] = 0; //The leading vertex of vertex I is 0
        }

        //Remove vs from u (u used with flag)
        flag[vs] = true;
        U[vs] = 0;
        //Add vs vertices to s
        S[0] = vertexes[vs];
        //Step one is over
        //Step 4: repeat step 2 and 3 until all vertices are traversed.
        //Traversal vertexes.length -Find the shortest path of one vertex at a time.
        int k = 0;
        for (int i = 1; i < vertexes.length; i++) {
            //Step 2: find the vertex with the shortest path from u and add it to s (if there is a shorter path from vs vertex to x vertex, then
            //There must be a path from y vertex to vs vertex which is shorter than the former and is not added to s
            //Therefore, the path of the shortest vertex in U is the shortest path of the vertex.)
            //In other words, among the vertices that have not obtained the shortest path, the vertex (k) nearest to VS is found.
            double min = Double.MAX_VALUE;
            for (int j = 0; j < vertexes.length; j++) {
                if (flag[j] == false && U[j] < min) {
                    min = U[j];
                    k = j;
                }
            }
            //Put K in S
            S[i] = vertexes[k];
            //Step 3: update the vertex in U and the path corresponding to the vertex
            //Mark "vertex K" as having obtained the shortest path (update the vertex in U, that is, mark the flag corresponding to vertex K as true)
            flag[k] = true;

            //Fix the current shortest path and the front drive vertex (update the path corresponding to the remaining vertices in U)
            //That is, when the " The shortest path of vertex K " After that, update " The shortest path and leading vertex of the vertex without getting the shortest path "。
            for (int j = 0; j < vertexes.length; j++) {
                //Connect other vertices with the position of K vertex, judge whether other vertices pass through the shortest path vertex K to vs vertex is less than the current shortest path, yes, update into u, no, no processing
                double tmp = (getPrim(k, j, int2Index, roadHashMap) == Double.MAX_VALUE ? Double.MAX_VALUE : (min + getPrim(k, j, int2Index, roadHashMap)));
                if (flag[j] == false && (tmp < U[j])) {
                    U[j] = tmp;
                    //Update the shortest path of vertex J, and the leading vertex is K
                    prev[j] = k;
                }
            }

        }
        System.out.print("shortest path（" + vertexes[vs].IntersectionId + "," + vertexes[end].IntersectionId + "):" + U[end] + "  ");
        List<Intersection> path = new ArrayList<>();
        int j = end;
        while (true) {
            if (j == 0) {
                path.add(vertexes[vs]);
                break;
            }
            path.add(vertexes[j]);
            j = prev[j];
        }
        String pre = null;
        for (int x = path.size() - 1; x >= 0; x--) {
            if (x == 0) {
                System.out.print(path.get(x).IntersectionId);
            } else {
                System.out.print(path.get(x).IntersectionId + "->");
            }
            if (pre != null) {
                res.add(roadHashMap.get(pre + path.get(x).IntersectionId));
            }
            pre = path.get(x).IntersectionId;
        }
        return res;
    }

    private static double getPrim(int i, int j, HashMap<Integer, Intersection> int2Index, HashMap<String, Road> roadHashMap) {

        String index = int2Index.get(i).IntersectionId + int2Index.get(j).IntersectionId;
        if (roadHashMap.containsKey(index)) {
            return roadHashMap.get(index).distance;
        } else {
            return Double.MAX_VALUE;
        }

        //            for (int i1 = 0; i1 < prim.length; i1++) {
//                //inner loop traverses elements of each one-dimensional array
//                for (int j = 0; j < prim[i1].length; j++) {
//                    if (prim[i1][j] == 0 && i1 != j) {
//                        prim[i1][j] = Double.MAX_VALUE;
//                    }
//                }
//            }
    }

//    public static void main(String[] args) {
//        Dijkstra dij = new Dijkstra();
//        dij.createGraph1(6);
////        dij.createGraph2(9);
//        dij.dijkstra(0, 3);
//    }


    public static ArrayList<Road> dijkstra(HashMap<String, ConnectList> connectListHashMap, HashMap<String, Road> roadHashMap) {

        Intersection start = Graph.allIntersectionMap.get(Graph.begin);
        PriorityQueue<Intersection> notVisite = new PriorityQueue<Intersection>(Graph.allIntersectionMap.size(),
                new Comparator<Intersection>() {
                    @Override
                    public int compare(Intersection i1, Intersection i2) {
                        if (i1.distance < i2.distance) {
                            return -1;
                        } else {
                            return 1;
                        }
                    }
                }
        );
        for (Map.Entry<String, Intersection> entry : Graph.allIntersectionMap.entrySet()) {
            notVisite.add(entry.getValue());
        }
        notVisite.remove(start);
        start.distance = 0;
        notVisite.add(start);
        int notVisiteVCount = Graph.allIntersectionMap.size();
        while (notVisiteVCount > 0) {
            Intersection temp = notVisite.remove();
            temp = Graph.allIntersectionMap.get(temp.IntersectionId);
            temp.visitable = true;
            notVisiteVCount = notVisiteVCount - 1;
            ConnectList connectList = connectListHashMap.get(temp.IntersectionId);
            E2 currentRoad = connectList.topV2.e2;
            Intersection currentIntersection;
            while (currentRoad != null) {
                if (currentRoad.road.intersect1.equals(temp.IntersectionId)) {
                    currentIntersection = Graph.allIntersectionMap.get(currentRoad.road.intersect2);
                } else {
                    currentIntersection = Graph.allIntersectionMap.get(currentRoad.road.intersect1);
                }
                if (currentIntersection.visitable == false) {
                    ConnectList temp2 = connectListHashMap.get(temp.IntersectionId);
                    double distance = temp2.getDistance(currentIntersection);
                    if (temp.distance + distance < currentIntersection.distance) {
                        notVisite.remove(currentIntersection);
                        currentIntersection.distance = temp.distance + distance;
                        currentIntersection.path = temp;
                        notVisite.add(currentIntersection);
                    }
                }
                currentRoad = currentRoad.nextE2;
            }
        }

        //Query path by end line
        Intersection temp = Graph.allIntersectionMap.get(Graph.end);
        ArrayList<Road> roads = new ArrayList<>();
        Intersection pre = null;
        double allDis = 0;
        System.out.println("the min path is ");
        while (temp.path != null) {
            Intersection curr = Graph.allIntersectionMap.get(temp.IntersectionId);
            if (pre != null) {
                Road road = roadHashMap.get(pre.IntersectionId + curr.IntersectionId);
                roads.add(road);
                allDis = allDis + road.distance;
            }
            pre = curr;
            temp = temp.path;
        }
        Road road = roadHashMap.get(pre.IntersectionId + Graph.begin);
        roads.add(road);
        allDis = allDis + road.distance;
        for (int i = roads.size() - 1; i >= 0; i--) {
            System.out.println(roads.get(i).intersect2 + "==>" + roads.get(i).intersect1 + "(" + roads.get(i).roadId + ")");
        }
        System.out.println("the minTree distance is " + allDis);
        return roads;
    }
}
